package com.zds.leetcode;

import java.util.ArrayList;
import java.util.List;

public class q_22 {
    public static void main(String[] args) {
        q_22 q_22 = new q_22();
        List<String> strings = q_22.generateParenthesis(3);
        System.out.println(strings);
    }


    List<String> res = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        // 回溯法
        // 这里判断的时候其实 左括号和右括号的数量是固定的
        generate(2*n, n, n, "");
        return res;
    }

    /**
     * 生成括号
     * @param max 最后结果的数量
     * @param l 剩余的左括号
     * @param r 剩余的右括号
     * @param track
     */
    public void generate(int max, int l, int r, String track){
        // 出现右括号比左括号多的情况 或者 左右括号使用完了 直接退出
        // 需要多用一点左括号（剩余的右括号需要大于等于左括号），才能保证一直闭合，有点像dp?
        // 反之，剩余的右括号如果小于左括号，那么就会出现不闭合的情况
        if (l > r || l < 0 || r < 0) {
            return;
        }
        if (track.length() == max) {
            res.add(track);
            return;
        }
        // 深度优先遍历
        generate(max, l - 1, r, track + "(");
        generate(max, l, r - 1, track + ")");
    }
}
